package Demo88;

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 最小基因变化
 * https://leetcode.cn/problems/minimum-genetic-mutation/submissions/563985094/
 */

class Solution {

    public int minMutation(String startGene, String endGene, String[] bank) {
        HashSet<String> vis = new HashSet<>();
        HashSet<String> hash = new HashSet<>();
        char[] change = {'A','C','G','T'};
        // 将基因库放入到set中
        for(String str : bank) {
            hash.add(str);
        }
        // 处理边界问题
        if(startGene.equals(endGene)) return -1; // 进化结果和初始一样
        if(!hash.contains(endGene))  return -1; // 进化结果不在基因库里
        Queue<String> q = new LinkedList<>();
        q.add(startGene);
        vis.add(startGene);
        int ret = 0;

        while(!q.isEmpty()) {
            ret++;
            int sz = q.size();
            while(sz-- != 0) {
                String t = q.poll();
                for(int i = 0; i < 8; i++) {
                    char[] tmp = t.toCharArray();
                    for(int j = 0; j < 4; j++) {
                        tmp[i] = change[j];
                        String next = new String(tmp);
                        if(hash.contains(next) && !vis.contains(next)) {
                            if(next.equals(endGene)) return ret;
                            q.add(next);
                            vis.add(next);
                        }
                    }
                }
            }
        }
        return -1;
    }
}
class Demo {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int ret = solution.minMutation("AAAAACCC", "AACCCCCC", new String[]{"AAAACCCC","AAACCCCC","AACCCCCC"});
        System.out.println(ret);
    }
}